第八章 查找                                                             

一、填空题

1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是                           。
2. 线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索      次。设有100个结点，用二分法查找时，最大比较次数是        。
3. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素                                    比较大小。
4. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是                      。

二、单项选择题

（     ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为
         A. ASL＝ｎ            B. ASL＝（ｎ＋1）／2            C. ASL＝＋1            D. ASL≈ｌｏｇ２（ｎ＋1）－1
（     ）2． 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中          比较大小，查找结果是失败。
         A．20，70，30，50            B．30，88，70，50            C．20，50            D．30，88，50
（     ）3． 对22个记录的有序表作折半查找，当查找失败时，至少需要比较        次关键字。
         A．3            B．4            C．5            D． 6

          4.  数据结构反映了数据元素之间的结构关系。链表是一种   A   ，它对于数据元素的插入和删除   B   。通常查找线性表数据元素的方法有   C   和   D   两种方法，其中   C   是一种只适合于顺序存储结构但   E   的方法；而   D   是一种对顺序和链式存储结构均适用的方法。          
         供选择的答案：
         A：①顺序存储线性表  ②非顺序存储非线性表       ③顺序存储非线性表   ④非顺序存储线性表
         B：① 不需要移动结点，不需改变结点指针      ②不需要移动结点，只需改变结点指针      
              ③只需移动结点，不需改变结点指针            ④既需移动结点，又需改变结点指针
         C：① 顺序查找    ②循环查找        ③条件查找         ④二分法查找
         D：① 顺序查找    ②随机查找        ③二分法查找          ④分块查找
         E：① 效率较低的线性查找 ②效率较低的非线性查找   ③效率较高的非线性查找 ④效率较高的线性查找
         答案：A＝             B＝          C＝           D＝             E＝              

三、简答题

1. 对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？

2. 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

（1）画出描述折半查找过程的判定树；

（2）若查找元素54，需依次与哪些元素比较？

（3）若查找元素90，需依次与哪些元素比较？

（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。

四、分析题

1.  在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。